package 回溯;

import java.util.HashMap;

public class leetcode560和为k的子数组 {
	/**
	 * 前缀和 数组 加 哈希表的 优化 
	 * HashMap 中的 getOrDefault方法 其实 看名字 就明白作用是什么了
	 * 
	 * 
	 * @param args
	 */
	
//	HashMap
	
	
	
	  public static void main(String args[]) {
		int nums[] = {1,2,3};
//		System.out.println(solution(nums,3));
		getPreSum(nums);
		
	}
	/**
	 * {1} {2} {3}  这样单独 的 也是 子数组
	 * @param nums
	 * @param k
	 * @return
	 */
       public  static int solution(int nums[],int k) {
		int len = nums.length;
		int ans=0;
		int sum;
		// 排序好像是可以 剪枝 但是 结果 会错吧
		for(int i = 0; i < len;i++) {
			sum = 0;
			for(int j = i;j < len;j++) {
				sum+=nums[j];
				if(sum > k) {
					// 可能存在负数  这里这样写 break 就是错的 
					break;
				}
				if(sum==k) {
					ans++;
//					break;  时间复杂度 O（n^2）
				}
			}
		}
		return ans;
	}
       /**
        * 优化 的  前提  是要明白 时间 耗费 在那个地方  或者  那个地方 做了  多余 的 重 复的 过程
        * 一般是 重复的  操作 非常的多
        * 前缀数组   preSum []   前缀和数组 中存在 这样的 情况 preSum[i] <= preSum[i-1]
        * becase  nums[i] maybe <=0; 
        * i ......j 之间 有符合 题意的 子数组 则 preSum[j] - preSum[i-1] = k
        * 则说明   k  就是 这个 子数组的和     则 preSum[j] - k = preSum[i-1] 将问题转化了 
        * Hash Map 表 的作用就是来记录 preSum[i-1] 出现的次数  优化 不就是在这里 
        * 想不明白这个过程啊  熟悉一下 哈希表 做缓存表的  实例作用
        * 加上  Hash Map的优化  这个优化 很是 细节 说实话
        * 时间复杂度 为 O（N）
        */
       //前缀和数组  的求法       本质上是 动态规划
       public static void getPreSum(int nums[]) {
    	   int len = nums.length;
    	   int preSum[] = new int[len+1];
    	   System.out.println(preSum[0]);
    	   preSum[0] = 0;
		   HashMap<Integer,Integer> map = new HashMap<>();
    	   for(int i = 0; i < len;i++) {
    		   // 这一步 是不是非常熟悉        这不就是      熟悉的状态转移方程吗
    		   preSum[i+1] = preSum[i] + nums[i];
			   map.put(preSum[i + 1],map.getOrDefault(preSum[i + 1],0));
    	   }
    	   for(int num : preSum) {
    		   System.out.print(num+" ");
    	   }
       }
       public static int solutionPlus(int nums[],int k) {
    	   int preSum = 0;
    	   int count = 0;
    	         // preSum  --> times
    	   HashMap<Integer,Integer> map =new HashMap<>();
    	   map.put(0, 1);// 前缀和  为 0  出现了一次
    	   for(int num : nums) {
    		   preSum+=num;
    		   if(map.containsKey(preSum - k)) {
    			  count+=map.get(preSum - k); 
    		   }
    		   map.put(preSum,map.getOrDefault(preSum,0)+1);
    	   }
    	   return count;
       }
}
